1870E - Another MEX Problem - CodeForces Solution

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
#define x first
#define y second

using namespace std;

const int N = 5010, M = N*2, mod = 998244353, INF = 0x3f3f3f3f3f3f3f3f,P = 131;

//typedef __int128 LL;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<long long , long long> PLL;
typedef pair<char,int> PCI;
typedef pair<int,char> PIC;
typedef pair<int,pair<int,int>> PIII;
typedef pair<string,int> PSI;
typedef pair<double,double> PDD;

int n,m;
int a[N];
bool f[N][N];
bool st[N][N];
bool st2[N];

void solve()
{
    cin>>n;
    for (int i=1;i<=n;i++)cin>>a[i];
    
   // vector<vector<bool>> f(n+10,vector<bool>(n+10));
    //vector<vector<bool>> st(n+10,vector<bool>(n+10));
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
            f[i][j]=st[i][j]=0;
    
    int ans = 0;
    f[0][0]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=n;j++)st2[j]=0;
        for (int j=0;j<=n;j++)f[i][j]=f[i-1][j];
        //vector<bool> st2(n+10);
        //f[i]=f[i-1];
        int mex = 0;
        for (int j=i;j;j--)
        {
            st2[a[j]]=true;
            if(st2[mex])
            {
                while (st2[mex])mex++;
                if(st[j][mex])continue;
                st[j][mex]=true;
                for (int k=0;k<=j;k++)
                    if(f[j-1][k])
                    {
                        f[i][mex^k]=true;
                    }
            }
        }
        for (int j=0;j<=i;j++)
            if(f[i][j])ans = max(ans,j);
    }
    cout<<ans<<endl;
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    //init(N-1);
    int T=1;
    //scanf("%lld",&T);
    cin>>T;
    while (T--) solve();
    return 0;
}